package com.sheng.leetcode.year2023.month05.day19;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/05/19
 * <p>
 * 1079. 活字印刷<p>
 * <p>
 * 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。<p>
 * 注意：本题中，每个活字字模只能使用一次。<p>
 * <p>
 * 示例 1：<p>
 * 输入："AAB"<p>
 * 输出：8<p>
 * 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。<p>
 * <p>
 * 示例 2：<p>
 * 输入："AAABBC"<p>
 * 输出：188<p>
 * <p>
 * 示例 3：<p>
 * 输入："V"<p>
 * 输出：1<p>
 * <p>
 * 提示：<p>
 * 1 <= tiles.length <= 7<p>
 * tiles 由大写英文字母组成<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/letter-tile-possibilities">1079. 活字印刷</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1079 {

    @Test
    public void test01() {
        String tiles = "AAB";
//        String tiles = "AAABBC";
//        String tiles = "V";
        System.out.println(new Solution().numTilePossibilities(tiles));
    }
}

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] cnt = new int[26];
        for (char c : tiles.toCharArray()) {
            cnt[c - 'A']++;
        }
        return dfs(cnt);
    }

    /**
     * 表示当前剩余字母的计数为 cnt 时，能够组成的不同序列的个数
     *
     * @param cnt 表示每种字符的计数
     * @return 能组成的不同字符串的个数
     */
    public int dfs(int[] cnt) {
        int res = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > 0) {
                res++;
                // 表示使用的这个字符
                cnt[i]--;
                // 进行下一层搜索并累加返回的个数
                res += dfs(cnt);
                // 回溯
                cnt[i]++;
            }
        }
        return res;
    }
}
